package com.example.trie35;

/**
 * @description 基于英文构建 Trie 树，做全匹配
 * @auther lijiewei
 * @date 2022/1/14 16:06
 */
public class Trie {

    private TrieNode root = new TrieNode('/');

    /**
     * 往 Trie 树中插入一个字符串
     * @param text 字符串数组
     * @return
     * @author lijiewei
     * @date   2022/1/14 16:11
     */
    public void insert(char[] text) {
        TrieNode p = root;
        for (int i = 0; i < text.length; i++) {
            int index = text[i] - 'a';
            //没有对应子节点
            if (p.children[index] == null) {
                //同时设置了节点对应字符
                TrieNode newNode = new TrieNode(text[i]);
                p.children[index] = newNode;
            }
            //向下遍历
            p = p.children[index];
        }
        //是结束字符
        p.isEndingChar = true;
    }

    /**
     * 在 Trie 树中查找一个字符串
     * @param pattern 要查找的字符串
     * @return
     * @author lijiewei
     * @date   2022/1/14 16:27
     */
    public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 'a';
            //没有子集, 没有匹配
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndingChar == false) {
            //不能完全匹配，只是前缀
            return false;
        } else {
            return true;
        }
    }
}
